package cn.rocky.prepare;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 121. 买卖股票的最佳时机
 */
public class maxProfit {

    public static void main(String[] args) {
        int[] req = new int[]{7,1,5,3,6,4};
        System.out.println(maxProfit(req));
    }

    public static int maxProfit(int[] prices) {
        int n = prices.length;
        if(n == 1) {
            return 0;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        int ans = 0;
        int diffval = 0;
        stack.push(prices[0]);
        int bot = prices[0];
        for (int i = 1; i <= n - 1 ; i++) {
            if (prices[i] < stack.peek()) {
                //如果数组当前元素比栈顶小，开始循环弹出直到大于栈底元素，可能栈完全弹空
                while (!stack.isEmpty()) {
                    if (prices[i] >= stack.peek()) {
                        diffval = prices[i] - bot;
                        stack.push(prices[i]);
                        break;
                    }
                    stack.pop();
                }
                //栈完全弹空，试图刷新max值，重新加入栈并更新栈底元素
                if(stack.isEmpty()) {
                    ans = Math.max(ans, diffval);
                    bot = prices[i];
                    stack.push(prices[i]);
                }
            } else {
                //如果数组当前元素比栈顶大，减去栈底元素求得当前差值，并更新max值
                diffval = prices[i] - bot;
                ans = Math.max(ans, diffval);
                stack.push(prices[i]);
            }
        }
        return ans;
    }


    public int maxProfit1(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}
